struct Node
{
    int key;
    int value;
    Node*next;
    Node*prev;
    Node(int k=0,int v=0):key(k),value(v){}
};

class LRUCache {
    private:
    void remove(Node* x) {
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }

    // 在链表头添加一个节点（把一本书放到最上面）
    void push_front(Node* x) {
        x->prev = dummy;
        x->next = dummy->next;
        x->prev->next = x;
        x->next->prev = x;
    }

    // 获取 key 对应的节点，同时把该节点移到链表头部
    Node* get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) { // 没有这本书
            return nullptr;
        }
        Node* node = it->second; // 有这本书
        remove(node); // 把这本书抽出来
        push_front(node); // 放到最上面
        return node;
    }
public:
       
    LRUCache(int capacity):  _capacity(capacity),dummy(new Node())
    {
        dummy->next=dummy;
        dummy->prev=dummy;
    }
    
    int get(int key) {
        Node*node=get_node(key);
        return node?node->value:-1;
    }
    
    void put(int key, int value) {
        Node*node=get_node(key);
        if(node)
        {
            node->value=value;
            return;
        }
        key_to_node[key]=node=new Node(key,value);
        push_front(node);
        if(key_to_node.size()>_capacity)
        {
            Node*back_node=dummy->prev;
            key_to_node.erase(back_node->key);
            remove(back_node);
            delete back_node;
        }
    }
    private:
        int _capacity;
        Node*dummy;//哨兵
        unordered_map<int,Node*> key_to_node;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */